A cryptographic algorithm is an algorithm that aims to protect information, for example by ensuring its confidentiality, its authenticity, or its integrity, through mathematics. A cryptographic algorithm is often based on one or more keys, which can be secret, private, or public. Some cryptographic algorithms do not use a key, which is true for certain hash functions (such as SHA-1, MD5, SHA-256, RIPEMD-160, etc.). Cryptographic algorithms include encryption algorithms (which render information unintelligible) and decryption algorithms (which recover the original information from encrypted information), algorithms for e-signature, signature verification, authentication and authentication verification, etc. Some of the cryptographic algorithms which are key-based are referred to as symmetric (for example the algorithms DES, 3DES, AES, RC4, HMAC, etc.). Some symmetric algorithms are specialized (for example the HMAC algorithm is used for signature/signature verification, but not for encryption/decryption). Symmetric algorithms derive their name from the fact that they use the same key (generally referred to as a secret key) for encryption and decryption, or for signing or verifying a signature, etc. Symmetric cryptographic algorithms therefore require that the two parties using them secure their communications using shared keys. The AES (Advanced Encryption Standard) algorithm is significant because this is the algorithm that was chosen in 2000 by NIST to become the standard symmetric encryption algorithm for the government of the United States of America. Other cryptographic algorithms are referred to as asymmetric (for example DSA, RSA, elliptic curve and other algorithms) because a different key is used by the parties to a communication. Each party has a private key and an associated public key. For example, one party can use one of its private keys to sign a piece of information and the corresponding public key is used by the other party to verify the signature, or one party can use the public key belonging to another party to encrypt a piece of information, and the other party can then use its corresponding private key to decrypt the piece of information.
Cryptographic algorithms are often described in a very precise manner in specifications accessible to everyone, as the security of a cryptographic algorithm is generally not related to any secrecy in how it operates (algorithms which are assumed to be secure due solely to their secrecy are often ultimately cracked by reverse engineering). The specifications determine what an algorithm must produce as output when it is provided with certain information as input. This ensures the interoperability of the cryptographic algorithm, meaning that different implementations must function reciprocally. For example, one can reasonably expect that information encrypted by any implementation of an encryption algorithm should be decrypted by any implementation of the corresponding decryption algorithm. This does not mean that there is only one possible implementation of each cryptographic algorithm, however. Quite the contrary: there are many possible implementations of each cryptographic algorithm, and there are a multitude of different ways to perform the same calculation. For example, in order to calculate X2+2X+1, it is possible to first calculate X*X, then 2*X, then add these two terms and then add 1, or to calculate X+1, multiply the result by X, and then add 1, or even to calculate X−1 and square the result.
One might think that the security of a cryptographic algorithm depends only on its mathematical definition (and any keys that are used, whether secret or private) as disclosed in the specification, and not on the exact method which is used to calculate the result defined in the specification. In reality, this is generally not so. It turns out that the security of a particular implementation of a cryptographic algorithm depends not only on the actual cryptographic algorithm, but also on the manner in which it is implemented and on other factors such as the characteristics of the electronic device used to execute it.
In particular, it is well known that when an unprotected electronic device runs software implementing a cryptographic algorithm in a “naive” manner, meaning that it does no more than simply produce the numerical result expected according to the specification (such as an encryption result) from a given input, it is generally possible to perform passive electronic eavesdropping or sniffing of the electronic device and to obtain critical information about the cryptographic algorithm's execution. The advantage of passive sniffing is that it is non-invasive. The electronic device is not damaged, and its owner may not necessarily be aware that he was attacked. The device could have been appropriated and returned without the owner suspecting it, or simply used in the owner's absence, or even spied upon in the presence of the owner without the owner being aware (for example by a module concealed between the electronic device and its power source). Therefore, the owner of an electronic device from which a private RSA key was extracted by an attacker is not led to revoke his pair of RSA keys, as there is no reason to suspect an attack. The attacker can then freely use the RSA private key until the owner finally realizes that operations he had not performed (for example electronic funds transfers, or electronic signature of contracts) have been attributed to him, or that a third party has clearly had access to confidential information (for example multiple occurrences of the same competitor underbidding on requests for proposals by a very small amount).
Passive sniffing can consist, for example, of analyzing electromagnetic radiation emitted by the device while it executes the software (for example as part of a TEMPEST attack, which is generally focused on capturing emanations from CRT displays but can be more general). Indeed, electromagnetic radiation from an electronic device, for example a processor, depends on what the processor is currently executing, such as an instruction the processor is currently executing or data the processor is currently processing. It is also possible to analyze other types of information, such as the instantaneous power consumption of an electronic device, and use this to distinguish what tasks are being performed based on the electrical power required by these tasks. It is also possible to measure emitted vibrations (some components are susceptible to vibrating differently depending on what is being performed), as well as temperature variations, etc.
Passive sniffing can also include an analysis of the time required to execute certain operations. Passive sniffing draws conclusions from this analysis, when these operations are not protected against attacks referred to as “timing attacks”. For example, a password verification operation unprotected against timing attacks might compare the bytes of a submitted password with the bytes of the expected password, byte by byte, and return an error when a byte is different. Based on the time required for the verification function to respond that the password is incorrect, an attacker could deduce that the first N bytes are correct, and retry by submitting a probable password with only the N+1 byte modified, until the response time slows down somewhat which would indicate that the N+1 byte is now correct, at which point he would move on to the N+2 byte, and so on until the complete password is obtained. Here, in order to guess a password having a length K (in bytes), even when it is a strong password (dictionary attacks not possible), the average complexity decreases from ½*(28)K to a much simpler average complexity of K*27. In order to avoid timing attacks, it is possible to ensure that all sensitive operations have a constant execution time, or that although the duration may be variable it provides no information on what is occurring during the operation. Additional countermeasures are also possible: in the previous example, the password could be blocked after a certain number of failed attempts, which is the usual approach with PIN codes. However, generally these additional measures are merely a supplemental protection against timing attacks, not a substitute. For example, assuming that a bank card blocks a PIN code after five unsuccessful attempts but implements an unprotected verification as described above, someone (for example a teenager, an employee, etc.) could appropriate a bank card (for instance from his mother, his boss, etc.) each time the legitimate owner has made a transaction, for example payment for a business lunch in a restaurant (which resets the counter of unsuccessful attempts), and can then make four attempts each time. For a four-digit PIN code, it would thus take an average of twenty attempts (meaning that the card would have to be taken 5 times), and a maximum of forty attempts to find the PIN code, which would be fairly easy to carry out.
Basic sniffing can consist of simply identifying a specific characteristic from a specific measurement on the targeted electronic device. This is the case for example with so-called SPA (Simple Power Analysis) attacks. For example, in a modular exponentiation performed in a “naive” implementation of the RSA algorithm, the consumption of electricity is very different when a bit of the exponent is equal to 1 (high consumption) and when a bit is equal to 0 (lower consumption). In fact, in common implementations, a bit at 1 involves both a square operation and a multiplication operation (called “square and multiply”), while a bit at 0 only involves a square operation. By observing the trace of electricity consumption during modular exponentiation, one can thus identify series of 1s and 0s in the exponent which correspond to the fluctuations in the electricity consumption. The RSA exponent, in the case where this concerns a private exponent, is extremely confidential data that is a component of the private RSA key, which in general is not supposed to be known to anyone outside of the electronic device. Obtaining a person's private signature key thus allows signing in his name, and obtaining his private decryption key allows decrypting his messages.
However, these sniffing attempts (easy to implement) are not always effective. More elaborate sniffing techniques are known, such as the so-called DPA (Differential Power Analysis) techniques in which an attacker repeatedly executes a cryptographic algorithm, recording the traces produced each time (for example the power traces). Then the attacker makes statistical calculations based on multiple records and obtains information in a manner which is more reliable and more difficult to prevent.
To guard against such attacks, it is possible to add security measures to the electronic device itself. For example, noise can be superimposed onto the supplied power to make its analysis more difficult, the power consumption can be smoothed (for example with capacitors), the electromagnetic emissions can be limited by appropriate shielding, etc. It is also possible to use a special internal clock operating at a randomly selected variable frequency, which renders such measures difficult to use (because the operations of the cryptographic algorithms are then performed at a rate which keeps changing and which is not known to the attacker in advance). There are also other techniques, for example consisting of controlling the physical access and/or logical access to the electronic device. For example, smart cards implementing private key cryptographic algorithms generally protect relevant operations by a PIN code. A person who temporarily steals a smart card, hoping to extract the private key and then return the card without the owner being aware of this, would not be able to execute the relevant algorithm without providing the correct PIN (which an informed user knows by heart and does not reveal to anyone), and would thus not be able to carry out the attack.
These countermeasures are extremely useful, but are generally insufficient by themselves because they do not protect against all possible attack scenarios. Another protection method consists of using a security measure, with the cryptographic algorithm, which consists of implementing the algorithm in such a way that it generates minimum fluctuations (electrical or other fluctuations).
For example, it is possible to modify the implementation of a private key-based RSA algorithm so that it performs operations having the same signature (electric, electromagnetic, etc.) for a 1 bit or for a 0 bit in the private exponent of the private key. For example, it is possible to perform a square and multiply in all cases, and only use the result of the multiplication operation when the bit is 1. One obviously has to be very vigilant, and have the implementation to be as symmetrical as possible. For example, if there is a test that verifies whether or not the result of the multiplication should be used, this test must behave in the same manner regardless of its result (or at least in as similar a manner as possible), because passive sniffing could otherwise target this test to determine whether the bit is at 0 or at 1.
Another security measure (which can be used to supplement the previous one) consists of masking sensitive data. Sensitive data can be, for example, cryptographic keys, and/or an input message that is to be encrypted for example with the cryptographic algorithm, and/or certain intermediate data manipulated during the execution of the cryptographic algorithm. In some cases the attacker may know or choose an input message to be processed by the cryptographic algorithm, and can then make much more precise predictions concerning the current calculation. As the input message and/or intermediate data are masked in a manner that, in principle, is unpredictable by the attacker, this takes some of the information away from the attacker and can therefore significantly complicate the attack. Moreover, provided that the masking is different for each use of the cryptographic algorithm, the statistical analysis can be complicated. For example, several methods which protect by masking the AES algorithm have been proposed to protect against side-channel attacks. One traditional solution is additive masking, where the manipulated data x is replaced with masked data x+m (+ denoting here the exclusive OR). This easily passes through the linear operations of the algorithm. The substitution (nonlinear) tables S[ ] are then replaced with masked tables generated on the fly after drawing a new mask (or all pre-stored in memory if the amount of memory permits this). In this manner, a masked nonlinear operation corresponding to a masked substitution table S′[ ], applied to data x masked by a random mask m1, can be written in the following form:y′=S′[x+m1]=y+m2=S[x]+m2 
where m2 is a corresponding random mask which masks the output value of the substitution table. At the end of the algorithm, the result is unmasked to obtain the final result (the original data, encrypted and unmasked).
Nevertheless, attacks will sometimes successfully overcome the difficulties introduced by prior art masking. In particular, some types of attacks such as HO-DPA (High Order Differential Power Analysis) attacks can be especially difficult to avoid under certain circumstances. This is explained in particular in the article “On Second-Order Differential Power Analysis” by Marc Joye, Pascal Paillier and Berry Schoenmakers, published in Cryptographic Hardware and Embedded Systems, CHES 2005, Lecture Notes in Computer Science 3659 (2005), 293-308, Springer Verlag. Therefore, when an attacker successfully correlates power consumption (or other information of this type) with calculations multiple times, he can sometimes overcome the masking.